A bit (short for binary digit) is the smallest unit of information when it comes to computation. When you hear about 1s and 0s and binary and all that jazz, we're really talking about bits.

Since computers speak and understand in bits, it's important for us as developers to be familiar with the concept of a bit and what they represent. If you're not familiar with the transition between decimal numbers and binary numbers, I suggest you find a resource that will help you bridge that gap. It's a little beyond the scope of this article. This reminder should suffice: remember that 1 represents true and 0 represents false. This should help with the logic of the operations we'll discuss.

What we are going to explore is how to perform simple arithmetic operations on numbers using bit manipulation. Also, we'll take a look at some algorithmic problems that become trivial when we enter the wonderful world of bit manip. Let's dive in!

Bitwise Operators

Before we can dive into the cool, algorithmic stuff, we'll need to talk a little about bitwise operations that make bit manipulation possible. If you've taken a logic course, you'll understand some of the underlying principles behind these operations, but even without a logic background, they should be fairly straightforward.

Bitwise NOT

Also known as the complement, this operation forms the complement of a given bit. That is, if the bit is a 0, the result will be 1, and vice versa. It's pretty straightforward, especially thinking about it in the "1 is true, 0 is false" context. Not true is false, and not false is true. Let's take a look:

Grab some paper and try a couple for yourself:

Bitwise AND

Like the previous operation, bitwise AND is very straightforward. Think back to logic and program flow: 1 and 1 (true and true) is true, 1 and 0 (true and false) is false, and 0 and 0 (false and false) is false. Let's look at some examples:

Again, try some for yourself:

Bitwise OR

If you understood bitwise AND, it's not to far of a leap to make for bitwise OR. Think about how the logical OR operation works in program flow. I won't belabor it too much, but here are some examples:

And, if you care to practice for yourself a bit:

Bitwise XOR

As you'll soon see, the bitwise XOR operation is immensely useful for arithmetic operations. XOR returns true (1) if exactly one of the bits is true and the other is false. So, 1 and 1 returns 0, 0 and 0 returns 0, but 1 and 0 returns 1, as does 0 and 1. It's true if and only if exactly one bit is true. For example:

Notice how in the first example, XOR behaves almost like subtraction, and in the second case, it behaves almost like addition. We'll explore these interesting characteristics with some Python code in a bit. For now, try these examples to get the hang of how XOR works:

Bit shifting

The last bit manipulating operation we'll discuss here is a shift. We can shift bits to the left (<<) or right (>>) to varying effects. If we perform a left-shift on a number, each bit will be moved to the spot on the left, and the rightmost bit will be filled with a zero, like so:

Notice in the second example that the leftmost bit is lost. It's not carried over to the right as you might think. Instead, it's lost into the ether.

Right-shifts function similarly, only in the opposite direction. One important difference is that the leftmost bit is filled with the value of the most significant bit, which determines the sign of the number. Thus, positive numbers will stay positive and negative numbers will stay negative. Check out these examples:

Note that, like the left-shift, any bits that are pushed off the right side of the number are lost into the ether. And note in the second example that the value of the most significant bit is preserved, keeping the number negative.

That should be enough about bit shifting to get us started, but I highly recommend you seek to understand these concepts at a deeper level. This understanding will help you immensely in your CS learning.

On to the Algorithms

That should be enough of a primer to move into some cool algorithmic and mathematic tricks we can do with bit manipulation. If you want to learn more, check out Hacker's Delight. It has a lot of cool arithmetic techniques that should satiate all of your programming curiosity.